
#include <iostream>   // c++标准库
//#include <string.h> // c语言库
#include <cstring>    // c++改进自c语言的库
#include <stack>
#include <vector>
#include <queue>

// 邻接表表示的图
namespace {

#define MAX 100
#define LENGTH(a) (sizeof(a)/sizeof(a[0]))

typedef char DataType;
typedef struct _ENode {
    int ivex;                   // 该边指向的顶点的位置
    struct _ENode *next_edge;   // 指向下一条弧的指针
}ENode;

typedef struct _VNode {
    DataType data;              // 顶点数据
    ENode *first_edge;          // 指向第一条依附该顶点的弧
}VNode;

typedef struct _LGraph {
    int vexnum;                 // 顶点的数目
    int edgnum;                 // 边的数目
    VNode vexs[MAX];
}LGraph;

int get_position(const LGraph *pG, DataType ch) {
    for (int i=0; i<pG->vexnum; i++) {
        if (pG->vexs[i].data == ch)
            return i;
    }
    return -1;
}

void link_last(ENode **list, ENode *node) {
    ENode **p = list;
    while (*p)
        p = &(*p)->next_edge;
    *p = node;
}

LGraph* init_lgraph() {
    DataType vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
    DataType edges[][2] = {
        {'A', 'B'},
        {'B', 'C'},
        {'B', 'E'},
        {'B', 'F'},
        {'C', 'E'},
        {'D', 'C'},
        {'E', 'B'},
        {'E', 'D'},
        {'F', 'G'}
    };
    int vlen = LENGTH(vexs);
    int elen = LENGTH(edges);

    LGraph *pG;
    if ((pG = new LGraph()) == NULL) return NULL;
    memset(pG, 0, sizeof(LGraph));

    pG->vexnum = vlen;
    pG->edgnum = elen;

    // 初始化顶点
    for (int i=0; i<pG->vexnum; i++) {
        pG->vexs[i].data = vexs[i];
        pG->vexs[i].first_edge = NULL;
    }

    // 初始化边
    DataType c1, c2;
    int p1, p2;
    ENode *node1;
    for (int i=0; i<pG->edgnum; i++) {
        c1 = edges[i][0];
        c2 = edges[i][1];

        p1 = get_position(pG, c1);
        p2 = get_position(pG, c2);

        node1 = new ENode();
        node1->ivex = p2;

        // 将node1链接到"p1所在链表的末尾"
        link_last(&pG->vexs[p1].first_edge, node1);
    }

    return pG;
}

void print_lgraph(const LGraph *pG) {
    ENode *node;
    std::cout << "list graph" << pG->vexnum << pG->edgnum << std::endl;
    for (int i=0; i<pG->vexnum; i++) {
        std::cout << i << "(" << pG->vexs[i].data << "): ";
        node = pG->vexs[i].first_edge;
        while (node) {
            std::cout << node->ivex << "(" << pG->vexs[node->ivex].data << ") ";
            node = node->next_edge;
        }
        std::cout << std::endl;
    }
}

void dfs_loop(const LGraph *pG, int i, int visited[]) {
    visited[i] = 1;
    std::cout << pG->vexs[i].data;
    ENode *node = pG->vexs[i].first_edge;
    while (node) {
        if (!visited[node->ivex])
            dfs_loop(pG, node->ivex, visited);
        node = node->next_edge;
    }
}

// 深度遍历的递归实现
void dfs(const LGraph *pG) {
    int visited[MAX] = {0};     // 顶点访问标记

    std::cout << "dfs:  ";
    for (int i=0; i<pG->vexnum; i++) {
        if (!visited[i])
            dfs_loop(pG, i, visited);
    }
    std::cout << std::endl;
}

// 深度遍历的非递归实现（用stack结构）
void dfs2(const LGraph *pG) {
    int visited[MAX] = {0};     // 顶点访问标记

    std::cout << "dfs2: ";
    std::stack<int> st;
    int i = 0;
    visited[i] = 1;
    st.push(i);
    std::cout << pG->vexs[i].data;
    while (!st.empty()) {
        ENode *node = pG->vexs[st.top()].first_edge;
        while (node) { // 遍历到最后一个节点再回溯
            i = node->ivex;
            if (!visited[i]) {
                visited[i] = 1;
                st.push(i);
                std::cout << pG->vexs[i].data;
                node = pG->vexs[i].first_edge;
            }
            else {
                node = node->next_edge;
            }
        }
        st.pop();
    }
    std::cout << std::endl;
}

// 深度遍历的非递归实现（数组实现的栈）
void dfs3(const LGraph *pG) {
    int visited[MAX] = {0};     // 顶点访问标记
    int queue[MAX];
    int pos = 0;

    std::cout << "dfs3: ";
    int i = 0;
    visited[i] = 1;
    queue[pos++] = i;
    std::cout << pG->vexs[i].data;
    while (pos > 0) {
        ENode *node = pG->vexs[pos-1].first_edge;
        while (node) {
            i = node->ivex;
            if (!visited[i]) {
                visited[i] = 1;
                queue[pos++] = i;
                std::cout << pG->vexs[i].data;
                node = pG->vexs[i].first_edge;
            }
            else {
                node = node->next_edge;
            }
        }
        pos--;
    }
    std::cout << std::endl;
}

// 广度遍历（类似树的层次遍历，数组实现的队列）
void bfs(const LGraph *pG) {
    int visited[MAX] = {0};     // 顶点访问标记
    int queue[MAX];
    int head = 0;
    int rear = 0;

    std::cout << "bfs:  ";
    for (int i=0; i<pG->vexnum; i++) {
        if (!visited[i]) {
            visited[i] = 1;
            std::cout << pG->vexs[i].data;
            queue[rear++] = i; // 入队
        }
        while (head != rear) {
            int j = queue[head++]; // 出队
            ENode *node = pG->vexs[j].first_edge;
            while (node) { // 将该节点下的边全部遍历完毕
                j = node->ivex;
                if (!visited[j]) {
                    visited[j] = 1;
                    std::cout << pG->vexs[j].data;
                    queue[rear++] = j;
                }
                node = node->next_edge;
            }
        }
    }
    std::cout << std::endl;
}

// 岛屿数量问题
// https://leetcode-cn.com/problems/number-of-islands/
// 广度遍历方法
int numIslands(std::vector<std::vector<char>> &grid) {
    int count = 0;
    int row = grid.size();
    int col = grid[0].size();
    std::queue<std::pair<int, int>> que;
    for (int i=0; i<row; i++) {
        for (int j=0; j<col; j++) {
            if (grid[i][j] == 0) continue;
            grid[i][j] = 0;
            que.push(std::make_pair(i, j));
            ++count;
            while (!que.empty()) { // 遍历联通的所有节点，并置1
                auto key = que.front();
                que.pop();
                int r = key.first, c = key.second;
                if (r + 1 < row && grid[r + 1][c] != 0) {
                    grid[r + 1][c] = 0;
                    que.push({r + 1, c});
                }
                if (r - 1 >= 0 && grid[r - 1][c] != 0) {
                    grid[r - 1][c] = 0;
                    que.push({r - 1, c});
                }
                if (c + 1 < col && grid[r][c + 1] != 0) {
                    grid[r][c + 1] = 0;
                    que.push({r, c + 1});
                }
                if (c - 1 >= 0 && grid[r][c - 1] != 0) {
                    grid[r][c - 1] = 0;
                    que.push({r, c - 1});
                }
            }
        }
    }
    return count;
}

void numIslands2Sub(std::vector<std::vector<char>> &grid, int i, int j, int row, int col) {
    if (i < 0 || i >= row || j < 0 || j >= col || grid[i][j] == 0) return;
    grid[i][j] = 0;

    numIslands2Sub(grid, i + 1, j, row, col);
    numIslands2Sub(grid, i - 1, j, row, col);
    numIslands2Sub(grid, i, j + 1, row, col);
    numIslands2Sub(grid, i, j - 1, row, col);
}

// 递归法
int numIslands2(std::vector<std::vector<char>> &grid) {
    int count = 0;
    int row = grid.size();
    int col = grid[0].size();
    for (int i=0; i<row; i++) {
        for (int j=0; j<col; j++) {
            if (grid[i][j] == 0) continue;
            numIslands2Sub(grid, i, j, row, col);
            ++count;
        }
    }
    return count;
}

void Handle() {
    LGraph *pG;

    pG = init_lgraph();
    print_lgraph(pG);
    dfs(pG);
    dfs2(pG);
    dfs3(pG);
    bfs(pG);

    std::vector<std::vector<char>> grid = {
        {1,1,0,0,0},
        {1,1,0,0,0},
        {0,0,1,0,0},
        {0,0,0,1,1}
    };

    int num = numIslands(grid);
    std::cout << "num islands: " << num << std::endl;
}

}

void HandleGraph() {
    Handle();
}
